You are given an array of intervals, where intervals[i] = [starti, endi] and each starti is unique.
The right interval for an interval i is an interval j such that startj >= endi and startj is minimized.
Return an array of right interval indices for each interval i. If no right interval exists for interval i, then put -1 at index i.
Example 1:
Input: intervals = [[1,2]] Output: [-1] Explanation: There is only one interval in the collection, so it outputs -1.
Example 2:
Input: intervals = [[3,4],[2,3],[1,2]] Output: [-1,0,1] Explanation: There is no right interval for [3,4]. The right interval for [2,3] is [3,4] since start0 = 3 is the smallest start that is >= end1 = 3. The right interval for [1,2] is [2,3] since start1 = 2 is the smallest start that is >= end2 = 2.
Example 3:
Input: intervals = [[1,4],[2,3],[3,4]] Output: [-1,2,-1] Explanation: There is no right interval for [1,4] and [3,4]. The right interval for [2,3] is [3,4] since start2 = 3 is the smallest start that is >= end1 = 3.
Constraints:
1 <= intervals.length <= 2 * 104intervals[i].length == 2-106 <= starti <= endi <= 106- The start point of each interval is unique.
Average Rating: 4.00 (22 votes)
Solution
Approach 1: Brute Force
The simplest solution consists of picking up every interval in the set and looking for the the interval whose start point is larger(by a minimum difference) than the chosen interval's end point by scanning the complete set for every interval chosen. While scanning, we keep a track of the interval with the minimum start point satisfying the given criteria along with its index. The result obtained for every interval chosen is stored at the corresponding index in the res array which is returned at the end.
Complexity Analysis
-
Time complexity : O(n2). The complete set of n intervals is scanned for every(n) interval chosen.
-
Space complexity : O(n). res array of size n is used.
Approach 2: Using Sorting + Scanning
We make use of a hashmap hash, which stores the data in the form of a (Key, Value) pair. Here, the Key corresponds to the interval chosen and the Value corresponds to the index of the particular interval in the given intervals array. We store every element of the intervals array in the hash-map.
Now, we sort the intervals array based on the starting points. We needed to store the indices of the array in the hashmap, so as to be able to obtain the indices even after the sorting.
Now, we pick up every interval of the sorted array, and find out the interval from the remaining ones whose start point comes just after the end point of the interval chosen. How do we proceed? Say, we've picked up the ith interval right now. In order to find an interval satisfying the given criteria, we need not search in the intervals behind it. This is because the intervals array has been sorted based on the starting points and the end point is always greater than the starting point for a given interval. Thus, we search in the intervals only with indices j, such that i+1<j<n. The first element encountered while scanning in the ascending order is the required result for the interval chosen, since all the intervals lying after this interval will have comparatively larger start points.
Then, we can obtain the index corresponding to the corresponding interval from the hashmap, which is stored in the corresponding entry of the res array. If no interval satisfies the criteria, we put a -1 in the corresponding entry.
Complexity Analysis
-
Time complexity : O(n2).
- Sorting takes O(nlogn) time.
- For the first interval we need to search among n−1 elements.
- For the second interval, the search is done among n−2 elements and so on leading to a total of: (n−1)+(n−2)+...+1=2n.(n−1)=O(n2) calculations.
-
Space complexity : O(n). res array of size n is used. A hashmap hash of size n is used.
Approach 3: Using Sorting + Binary Search
We can optimize the above approach to some extent, since we can make use of the factor of the intervals array being sorted. Instead of searching for the required interval in a linear manner, we can make use of Binary Search to find an interval whose start point is just larger than the end point of the current interval.
Again, if such an interval is found, we obtain its index from the hashmap and store the result in the appropriate res entry. If not, we put a -1 at the corresponding entry.
Complexity Analysis
-
Time complexity : O(nlogn). Sorting takes O(nlogn) time. Binary search takes O(logn) time for each of the n intervals.
-
Space complexity : O(n). res array of size n is used. A hashmap hash of size O(n) is used.
Approach 4: Using TreeMap
In this approach, instead of using a hashmap, we make use of a TreeMap starts, which is simply a Red-Black Tree(a kind of balanced Binary Search Tree) . This Treemap start stores data in the form of (Key, Value) pair and always remain sorted based on its keys. In our case, we store the data such that the start point of an interval acts as the Key and the index corresponding to the interval acts as the value, since we are concerned with data sorted based on the start points, as discussed in previous approaches. Every element of the intervals array is stored in the TreeMap.
Now, we choose each element of the intervals array and make use of a function TreeMap.ceilingEntry(end_point) to obtain the element in the TreeMap with its Key just larger than the end_point of the currently chosen interval. The function ceilingEntry(Key) returns the element just with its Key larger than the Key(passed as the argument) from amongst the elements of the TreeMap and returns null if no such element exists.
If non-null value is returned, we obtain the Value from the (Key, Value) pair obtained at the appropriate entry in the res array. If a null value is returned, we simply store a -1 at the corresponding res entry.
Complexity Analysis
-
Time complexity : O(N⋅logN). Inserting an element into TreeMap takes O(logN) time. N such insertions are done. The search in TreeMap using
ceilingEntryalso takes O(logN) time. N such searches are done. -
Space complexity : O(N). res array of size n is used. TreeMap starts of size O(N) is used.
Approach 5: Using Two Arrays without Binary Search
Algorithm
The intuition behind this approach is as follows: If we maintain two arrays,
-
intervals, which is sorted based on the start points.
-
endIntervals, which is sorted based on the end points.
Once we pick up the first interval(or, say the ith interval) from the endIntervals array, we can determine the appropriate interval satisfying the right interval criteria by scanning the intervals in intervals array from left towards the right, since the intervals array is sorted based on the start points. Say, the index of the element chosen from the intervals array happens to be j.
Now, when we pick up the next interval(say the (i+1)th interval) from the endIntervals array, we need not start scanning the intervals array from the first index. Rather, we can start off directly from the jth index where we left off last time in the intervals array. This is because end point corresponding to endIntervals[i+1] is larger than the one corresponding to endIntervals[i] and none of the intervals from intervals[k], such that 0<k<j, satisfies the right neighbor criteria with endIntervals[i], and hence not with endIntervals[i+1] as well.
If at any moment, we reach the end of the array i.e. j=intervals.length and no element satisfying the right interval criteria is available in the intervals array, we put a -1 in the corresponding res entry. The same holds for all the remaining elements of the endIntervals array, whose end points are even larger than the previous interval encountered.
Also we make use of a hashmap hash initially to preserve the indices corresponding to the intervals even after sorting.
For more understanding see the below animation:
Complexity Analysis
-
Time complexity : O(N⋅logN). Sorting takes O(N⋅logN) time. A total of O(N) time is spent on searching for the appropriate intervals, since the endIntervals and intervals array is scanned only once.
-
Space complexity : O(N). endIntervals, intervals and res array of size N are used. A hashmap hash of size O(N) is used.
Why there is no heap approach?
O(NlogN) time and O(N) space as well.
import heapq
class Solution:
def findRightInterval(self, intervals: List[List[int]]) -> List[int]:
heap, result = [], [-1] * len(intervals)
for idx, interval in sorted(enumerate(intervals), key=lambda enum: enum[1]):
while heap and heap[0][0] <= interval[0]:
_, i = heapq.heappop(heap)
result[i] = idx
heapq.heappush(heap, (interval[1], idx))
return result
November 20, 2017 2:29 PM
The sorting + scanning approach's implementation does not match the description as the scanning does not stop at the first element found. In fact, by doing that I got that accepted without TLE.
This can also be solved using a 2 heap approach in O(NlogN) time. I'v added the comments in line with the code to make it understandable.
Here is the C++ code :
class Solution {
public:
vector<int> findRightInterval(vector<vector<int>>& intervals) {
priority_queue<pair<int,int>> endTimeMaxHeap;
priority_queue<pair<int,int>> startTimeMaxHeap;
vector<int>result(intervals.size());
//Create the max heap for both start and end times of the form <start,idx> and <end,idx>
for(int i = 0; i < intervals.size(); i++){
startTimeMaxHeap.push(make_pair(intervals[i][0], i));
endTimeMaxHeap.push(make_pair(intervals[i][1], i));
}
for(int i = 0; i < intervals.size(); i++){
//Add default answer first
result[endTimeMaxHeap.top().second] = -1;
//Check of we have a start entry that is greater than the current max end time
if(startTimeMaxHeap.top().first >= endTimeMaxHeap.top().first){
//Initialize the max start time element and pop it
auto startTop = startTimeMaxHeap.top();
startTimeMaxHeap.pop();
//Find the min start time entry that will satisfy the current max end time as the next interval.
//Discard all larger start time entries
while(!startTimeMaxHeap.empty() && startTimeMaxHeap.top().first >= endTimeMaxHeap.top().first){
startTop = startTimeMaxHeap.top();
startTimeMaxHeap.pop();
}
//Add the actual next interval since we found it
result[endTimeMaxHeap.top().second] = startTop.second;
//Re-add the top of start time max since it could be the next of an earlier end time
startTimeMaxHeap.push(startTop);
}
//Clear the end time entry since we processed it
endTimeMaxHeap.pop();
}
return result;
}
};
TreeMap/Heap are better than sorting based approaches only when the data is dynamic (with insertions/deletions). If the data is static, there is no reason to use these dynamic data structures instead of sorting.
August 28, 2020 11:02 AM
There is a typo in approach 2.
In order to find an interval satisfying the given criteria, we need not search in the intervals behind it.
We need to search precisely the intervals behind it, because the intervals are sorted by the starting points.
Can anyone help why the last example shows interval with same start point for two interval when the question clearly mentions otherwise?
August 28, 2020 1:27 AM
#4
q = [(intervals[i][0], i) for i in range(len(intervals))]
q.append((float('inf'), -1)) #centry
q.sort()
return [q[bisect.bisect_left(q, (r,-1))][1] for l, r in intervals]
good solution progression slowly building up the optimal!
Time Submitted | Status | Runtime | Memory | Language |
|---|---|---|---|---|
| 08/28/2020 09:40 | Accepted | 180 ms | 30.7 MB | cpp |
| 08/28/2020 09:39 | Accepted | 196 ms | 32.9 MB | cpp |
| 08/28/2020 09:37 | Wrong Answer | N/A | N/A | cpp |
xxxxxxxxxxclass Solution {public: vector<int> findRightInterval(vector<vector<int>>& intervals) { int n = intervals.size(); map<int, int>mp; vector<int>v; for(int i=0;i<n;i++) { mp[intervals[i][0]] = i; } for(auto it:intervals) { auto itr = mp.lower_bound(it[1]); if(itr == mp.end()) v.push_back(-1); else v.push_back(itr->second); } return v; }};

